package com.cty.huffmancode;

import java.util.*;

/*
 *
 * 创建赫夫曼编码树
 * */
public class huffmanCode {
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    static String Codes = "";

    public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        huffmanCode huffmanCode = new huffmanCode();
        List<Node> nodes = huffmanCode.nodes(str);
        Node huffmanTreeRoot = huffmanCode.createHuffmanTree(nodes);
        huffmanTreeRoot.preOrder();
        Map<Byte, String> codes = huffmanCode.getCodes(huffmanTreeRoot);
        System.out.println("赫夫曼编码" + codes);
    }

    private void preOrder(Node root) {
        if (root == null) {
            System.out.println("赫夫曼树为空");
            return;
        } else {
            root.preOrder();
        }
    }

    //为了方便调用重载一下
    private Map<Byte, String> getCodes(Node node) {
        if (node == null) {
            return null;
        } else {
            getCodes(node.left, "0", Codes);
            getCodes(node.right,"1", Codes);
        }
        return huffmanCodes;
    }

    //获得赫夫曼编码表
    private Map<Byte, String> getCodes(Node node, String path, String codes) {
        codes += path;
        if (node.data != null) {
            huffmanCodes.put(node.data, codes);
        } else {
            getCodes(node.left, "0", codes);
            getCodes(node.right, "1", codes);
        }
        return huffmanCodes;
    }

    //创建赫夫曼树
    private Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    //获得结点集合
    private List<Node> nodes(String str) {
        List<Node> nodes = new ArrayList<>();
        byte[] bytes = str.getBytes();
        Map<Byte, Integer> map = new HashMap<>();
        for (byte b : bytes) {
            Integer count = map.get(b);
            if (count == null) {
                map.put(b, 1);
            } else {
                map.put(b, count + 1);
            }
        }
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }
}
